package July;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;


public class Bipartite {
    public static void main(String[] args) {
        Solutions s = new Solutions();
    int[][] graph = new int[][]{{1,3},{0,2},{1,3},{0,2}};
    boolean res=s.isBipartite(graph);
    System.out.println(res);   
    }
}


class Solutions {
    Set<Integer> set0 = new HashSet<>();
    Set<Integer> set1 = new HashSet<>();
    boolean[] isVisited;
    public boolean isBipartite(int[][] graph) {
        isVisited = new boolean[graph.length];
        Arrays.fill(isVisited, false);
        for (int i = 0; i < graph.length; i++) {
            if(isVisited[i]==false){
                boolean re = search(graph, i , set0);
                if(re==false) return false;
            }
        }
        return true;
   }

   //搜索
   public boolean search(int[][] g,int start,Set<Integer> set){
       /**
        * set表示当前节点应该加入的集合
        */
       isVisited[start]=true;
       set.add(start);
        for (int p : g[start]) {
            if(set.contains(p)) return false; //表示两个已经被放入一个集合中了
            if(isVisited[p]==false){
                Set<Integer> newSet = set==set0?set1:set0;
                boolean res = search(g, p, newSet);
                if(!res) return false;
            }
            
        }
        return true;
   }
}